import java.util.ArrayList;
import java.util.Random;

public class Main {

    public static void main(String[] args) {

        BST<Integer> bst = new BST<>();
        int[] nums = {5, 3, 6, 8, 4, 2};
        for(int num: nums)
            bst.add(num);

        /////////////////
        //      5      //
        //    /   \    //
        //   3    6    //
        //  / \    \   //
        // 2  4     8  //
        /////////////////
        //前序遍历：递归
        bst.preOrder();
        System.out.println();
        System.out.println(bst);

        //前序遍历：非递归
//        bst.preOrderNR();
//        System.out.println();

        /**
         * 中序遍历的结果 =》就是按从小到大的顺序排列的结果
         */
//        bst.inOrder();
//        System.out.println();
//
//        bst.postOrder();
//        System.out.println();

        //层序遍历（广度优先遍历）
//        bst.levelOrder();
//        System.out.println(bst);

        // test removeMin

//        Random random = new Random();
//        int n = 1000;
//        for(int i = 0 ; i < n ; i ++)
//            bst.add(random.nextInt(10000));
//
//        ArrayList<Integer> nums = new ArrayList<>();
//        while(!bst.isEmpty())
//            nums.add(bst.removeMin());
//
//        System.out.println(nums);
//        for(int i = 1 ; i < nums.size() ; i ++)
//            if(nums.get(i - 1) > nums.get(i))
//                throw new IllegalArgumentException("Error!");
//        System.out.println("removeMin test completed.");


        // test removeMax
//        for(int i = 0 ; i < n ; i ++)
//            bst.add(random.nextInt(10000));
//
//        nums = new ArrayList<>();
//        while(!bst.isEmpty())
//            nums.add(bst.removeMax());
//
//        System.out.println(nums);
//        for(int i = 1 ; i < nums.size() ; i ++)
//            if(nums.get(i - 1) < nums.get(i))
//                throw new IllegalArgumentException("Error!");
//        System.out.println("removeMax test completed.");
    }
}
